/**
 * 一个方阵，三个人分别从三个 角出发，经过N-1步后都恰好要到达右下角
 * 问三个人拿到的总和最大是多少，一格的权值只能拿一次。
 * 左上角只能走主对角线，因此权值固定。
 * 其次，左下和右上的人只有可能在主对角线重合，而主对角线已经被拿走了，肯定为0
 * 也就是说这两个人互相不影响。
 * 因此可以分别DP
 * 令Dij是从起点到位置ij所能拿到的最大值，方程显然很简单，用刷表法即可
 */
class Solution {

using vi = vector<int>;

int N;
vector<vi> D;

public:
    int maxCollectedFruits(vector<vector<int>>& fruits) {
        N = fruits.size();
        int ans = 0;
        for(int i=0;i<N;++i) ans += fruits[i][i], fruits[i][i] = 0;
        ans += f(fruits);
        ans += g(fruits);
        return ans;
    }

    int f(vector<vi> & w){
        D.assign(N, vi(N, -1));
        D[N - 1][0] = w[N - 1][0];
        for(int j=0;j<N-1;++j){
            for(int i=N-1;i>=0;--i){            
                auto pre = D[i][j];
                if(pre != -1){
                    if(i - 1 >= 0){
                        chkmax(D[i - 1][j + 1], w[i - 1][j + 1] + pre);
                    }
                    chkmax(D[i][j + 1], w[i][j + 1] + pre);
                    if(i + 1 < N){
                        chkmax(D[i + 1][j + 1], w[i + 1][j + 1] + pre);
                    }
                }
            }
        }
        return D[N - 1][N - 1];
    }

    int g(vector<vi> & w){
        D.assign(N, vi(N, -1));
        D[0][N - 1] = w[0][N - 1];
        for(int i=0;i<N-1;++i){
            for(int j=N-1;j>=0;--j){
                auto pre = D[i][j];
                if(pre != -1){
                    if(j - 1 >= 0){
                        chkmax(D[i + 1][j - 1], w[i + 1][j - 1] + pre);
                    }
                    chkmax(D[i + 1][j], w[i + 1][j] + pre);
                    if(j + 1 < N){
                        chkmax(D[i + 1][j + 1], w[i + 1][j + 1] + pre);
                    }
                }
            }
        }
        return D[N - 1][N - 1];
    }

    void chkmax(int & a, int d){
        if(-1 == a or a < d) a = d;
    }
};